#include <algorithm>
#include <cstdio>

const int N = 100005;
int n, t;

struct Node {
  int dis, val, ch[2], f;
} tr[N];

inline int find(int x) { return tr[x].f == x ? x : tr[x].f = find(tr[x].f); }

inline int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (tr[x].val > tr[y].val || (tr[x].val == tr[y].val && x > y)) std::swap(x, y);
  tr[x].ch[1] = merge(tr[x].ch[1], y);
  tr[tr[x].ch[1]].f = x;
  if (tr[tr[x].ch[0]].dis < tr[tr[x].ch[1]].dis) std::swap(tr[x].ch[0], tr[x].ch[1]);
  tr[x].dis = tr[tr[x].ch[1]].dis + 1;
  return x;
}

inline void pop(int x) {
  static int ls, rs;
  ls = tr[x].ch[0], rs = tr[x].ch[1];
  tr[x].val = -1, tr[ls].f = ls, tr[rs].f = rs, tr[x].f = merge(ls, rs);
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#endif
#ifndef LOCAL
  freopen("LeftistTree.in", "r", stdin);
  freopen("LeftistTree.out", "w", stdout);
#endif
#endif

  scanf("%d%d", &n, &t);
  tr[0].dis = -1;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &tr[i].val);
    tr[i].f = i;
  }
  int opt, x, y;
  for (int i = 1; i <= t; ++i) {
    scanf("%d%d", &opt, &x);
    if (opt == 1) {
      scanf("%d", &y);
      if (tr[x].val != -1 && tr[y].val != -1) {
        int fx = find(x), fy = find(y);
        if (fx != fy) tr[fx].f = tr[fy].f = merge(fx, fy);
      }
    } else {
      if (tr[x].val == -1)
        printf("-1\n");
      else {
        printf("%d\n", tr[y = find(x)].val), pop(y);
      }
    }
  }
  return 0;
}